#include <bits/stdc++.h>
using namespace std;

const int N = 2000;
class Solution
{
  public:
    int mem[N][N];
    int dfs(vector<vector<int>> &matrix, int x, int y)
    {
        if (x == 0 && y == 0)
            return matrix[x][y];
        if (x < 0 || y < 0)
            return INT_MAX;
        if (mem[x][y])
            return mem[x][y];
        return mem[x][y] = matrix[x][y] +
                            min(dfs(matrix, x - 1, y), dfs(matrix, x, y - 1));
    }
    int minPathSum(vector<vector<int>> &matrix)
    {
        int n = matrix.size();
        int m = matrix.size();
        return dfs(matrix, n - 1, m - 1);
    }

};